package algorithm.linear;

/**
 * 顺序表
 * @param <E>
 */
public class SeqList<E> implements LList<E> {
    //对象数组
    private Object[] table;
    //顺序表长度
    private int n;

    public SeqList(int capacity) {
        this.table = new Object[capacity];
        this.n=0;
    }

    public SeqList() {
        this(16);
    }

    public boolean isEmpty() {
        return this.n == 0;
    }

    public int length() {
        return this.n;
    }

    public E get(int index) {
        if ( index >= 0 && index < this.n)
            return (E) this.table[index];
        return null;
    }

    public E set(int index, E element) {
        if ( index >= 0 && index < this.n && element!=null) {
            E old = (E) this.table[index];
            this.table[index] = element;
            return old;
        }
        return null;
    }

    /**
     * 在index位置插入element元素
     * @param index
     * @param element
     * @return 成功返回true,不能插入null
     */
    public boolean add(int index, E element) {
        if ( element == null ) {
            return false;
        }
        //扩容
        if ( this.n == table.length) {
            Object[] temp = this.table;
            //申请更大的数组
            this.table = new Object[temp.length *2];
            //复制数组
            for ( int i =0;i<temp.length;i++) {
                this.table[i] = temp[i];
            }
        }
        if (index < 0 )
            index = 0;
        if (index > this.n){
            index = this.n;
        }
        for(int j=this.n-1;j>index;j--)
            //元素后移
            this.table[j+1] = this.table[j];
        this.table[index] = element;
        this.n++;
        return true;
    }

    /**
     * 顺序表最后插入elememt元素
     * @param element
     * @return
     */
    public boolean add(E element) {
        //this.table[this.n] = element;
        return add(this.n,element);
    }

    public E remove(int index) {
        if (this.n!=0 && index >=0 && index<this.n){
            E old = (E) this.table[index];
            for(int j=index;j<this.n-1;j++) {
                this.table[j] = this.table[j+1];
            }
            this.table[this.n-1] = null;
            this.n--;
            return old;
        }
        return null;
    }

    public void clear() {
        if ( this.n!=0){
            for( int i=0;i<this.n;i++) {
                this.table[i] = null;
            }
            this.n = 0;
        }
    }

    public String toString() {
        String str = "(";
        if (this.n!=0) {
            for( int i=0;i<this.n-1;i++) {
                str += this.table[i].toString()+",";
            }
            //避免处理最后的逗号
            str += this.table[this.n-1].toString();
        }
        return str+")";
    }
    //顺序查询指定对象，返回位置 int
    public int indexOf(E element) {
        if(element!=null){
            for(int i=0;i<this.n;i++){
                if (this.table[i].equals(element)) {
                    return i;
                }
            }
        }
        return -1;
    }
    //查找结果是否包含指定对象 boolean
    public boolean contain(E element){
        return this.indexOf(element) > 0;
    }
}
